/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 */
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  // 暴力循环遍历
  // var max = '';
  // var len = s.length;
  // if (len < 2) return s;
  // for (var i = 0; i <= len; i++) {
  //   for (var j = 0; j <= len; j++) {
  //     var child = s.slice(i, j);
  //     console.log(child);
  //     var child_len = child.length;
  //     var max_len = max.length;
  //     var arr = child.split('');
  //     var str1 = arr.join();
  //     var str2 = arr.reverse().join();
  //     if (str1 === str2 && max_len < child_len) max = child;
  //     child = child_len = max_len = arr = str1 = str2 = null;
  //   }
  // }
  // return max;

  // 中心扩散 思路一：每个字符串都当成回文的中心
  if (s == null || s.length < 1) return '';

  let start = 0,
    end = 0; //记录长度
  for (let i = 0; i < s.length; i++) {
    let len1 = expandAroundCenter(s, i, i); //奇数回文的情况
    let len2 = expandAroundCenter(s, i, i + 1); //偶数回文的情况
    let len = Math.max(len1, len2);
    if (len > end) {
      start = i - Math.floor((len - 1) / 2);
      end = len;
    }
  }
  return s.substr(start, end);

  function expandAroundCenter(s, left, right) {
    let L = left,
      R = right;
    while (L >= 0 && R < s.length && s.charAt(L) == s.charAt(R)) {
      L--;
      R++;
    }
    return R - L - 1;
  }

  // 动态划分的方法（优化暴力方法中进行的不必要计算）（类似中心扩散的方法的逆推，4长度的回文串，掐头去尾之后长度二的必然也是回文，所有长度为3的回文一定是回文）
};

console.log(longestPalindrome('babadada'));
